package com.list;

import com.tgy.util.AbstractList;

/**
 * @Author: tgy
 * @Date: 2020-08-31 11:27
 */
public class DoubleWayLinkedList<E> extends AbstractList<E> {

    private Node<E> headNode;

    private Node<E> tailNode;

    private static  class Node<E>{

        private E element;

        private Node<E> pre;

        private Node<E> next;

        public Node(Node<E> pre, E element, Node<E> next) {

            this.pre = pre;
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public E get(int index) {

        return elementOf(index).element;
    }

    /**
     * 替换index位置的node
     * @param index
     * @param element
     * @return
     */
    @Override
    public E set(int index, E element) {

        Node<E> oldElement = elementOf(index);

        Node<E> currentNode = new Node<>(oldElement.pre, element, oldElement.next);

        if (oldElement.pre == null){

            headNode = currentNode;
        }else {
            oldElement.pre.next = currentNode;
        }

        if (oldElement.next == null){

            tailNode = currentNode;
        }else {

            oldElement.next.pre = currentNode;
        }

        return oldElement.element;
    }

    @Override
    public void add(int index, E element) {

        checkAddIndex(index);

        if (index == size){

            // 往最后插入
            tailNode = new Node<>(tailNode,element,null);

            // 如果 pre 不为 null 则说明tailNode前面还有节点，则把前面节点的 next指向当前节点
            if (tailNode.pre != null){

                tailNode.pre.next = tailNode;
            }

            if (headNode == null){

                headNode = tailNode;
            }

        }else {

            Node<E> nextNode = elementOf(index);

            Node<E> currentNode = new Node<>(nextNode.pre,element,nextNode);

            if (nextNode.pre == null){

                headNode = currentNode;
            }else {

                nextNode.pre.next = currentNode;
            }

            nextNode.pre = currentNode;
        }


        size++;

    }

    @Override
    public E remove(int index) {

        Node<E> removeNode = elementOf(index);


        if (removeNode.pre == null){

            // 链表头部
            headNode = removeNode.next;

        }else {

            removeNode.pre.next = removeNode.next;
        }

        if (removeNode.next == null){

            // 链表末尾
            tailNode = removeNode.pre;
        }else {

            removeNode.next.pre = removeNode.pre;
        }

        size--;
        return removeNode.element;
    }

    @Override
    public int indexof(E element) {

        if (element == null){

            Node<E> tmpNode  = headNode;
            for (int i = 0; i < size; i++) {

                if (element == tmpNode.element){

                    return i;
                }

                tmpNode = tailNode.next;
            }

        }else {

            Node<E> tmpNode  = headNode;
            for (int i = 0; i < size; i++) {

                if (element.equals(tmpNode.element)){

                    return i;
                }

                tmpNode = tailNode.next;
            }
        }

        return 0;
    }

    @Override
    public void clear() {

        // 没有 gc root 指向链表，会被gc回收
        headNode = null;
        tailNode = null;
        size = 0;

    }

    @Override
    public String toString() {


        StringBuilder stringBuilder = new StringBuilder("size = ");

        stringBuilder.append(size).append(" [ ");

        Node<E> tmpNode  = headNode;
        for (int i = 0; i < size; i++) {


            if (i != 0) {

                stringBuilder.append(", ");
            }

            if (tmpNode.pre == null){

                stringBuilder.append("null");
            }else {

                stringBuilder.append(tmpNode.pre.element);
            }


            stringBuilder.append("_").append(tmpNode.element).append("_");

            if (tmpNode.next == null){

                stringBuilder.append("null");
            }else {

                stringBuilder.append(tmpNode.next.element);
            }

            tmpNode = tmpNode.next;
        }

        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }

    private Node<E> elementOf(int index){

        checkIndex(index);
        Node<E> tmpNode = null;
        if (index <= size >> 1){

//            tmpNode = headNode;

            for (int i = 0; i <= index; i++) {

                if (i == 0){

                    tmpNode = headNode;
                }else {

                    tmpNode = tmpNode.next;
                }

            }

            return tmpNode;
        }else {

//            tmpNode = tailNode;

            for (int i = size; i > index; i--) {

                if (i == size){

                    tmpNode = tailNode;
                }else {

                    tmpNode = tailNode.pre;
                }
//                tmpNode = tmpNode.pre;
            }

            return tmpNode;
        }
    }
}
